In cloud computation, a client may want to store some data remotely and then have a remote server perform computations on that data. If the client does not wish to reveal this data, the nature of the computation, and the results of the computation to the remote server, then secure computation should be performed in order to process this remotely stored data.
In some approaches for performing secure computation, a program may need to be converted to a circuit, such as under the garbled circuits paradigm (see, for example Yao's garbled circuits in Andrew Chi-Chih Yao, “Protocols for secure computations” (extended abstract), in FOCS, pages 160-164, 1982) or the randomized encoding paradigm. However, many algorithms are more naturally and compactly represented as RAM programs, and converting these into circuits may lead to a significant increase in program size and execution time. Although there are polynomial transformations between time-bounded RAM programs and circuits, it is desirable to circumvent these transformation costs and execute RAM programs directly in a private manner, while retaining the same noninteractive properties as garbled circuits. It is also desirable to execute these RAM programs on the remote server without needing interaction with the client during program execution.
It is against this background that a need arose to develop the apparatus, system, and method described herein.